package cn.xiaolang.function.data_structure;

import lombok.extern.slf4j.Slf4j;

/**
 * 动态规划：零钱兑换 II
 *
 * @author Dean
 * @date 2021-06-15
 */
@Slf4j
public class DynamicProgramming {
    public static void main(String[] args) {
        DynamicProgramming temp = new DynamicProgramming();
        // 1，2，5 凑出 5 的可能性
        System.out.println(temp.change(5, new int[]{2, 1, 5}));
    }

    /**
     * 用 dp[x] 表示金额之和等于x的硬币组合数，目标是求 dp[amount]
     * 1 dp[0]=1 只有当不选取任何硬币时，金额之和才为 00，因此只有 11 种硬币组合
     * 2 遍历i从coin到amount，将 dp[i−coin] 的值加到dp[i]。
     * 3 最终得到 dp[amount] 的值即为答案。
     * <p>
     * 例如，coins=[1,2]，对于 dp[3] 的计算，一定是先遍历硬币面额1,后遍历硬币面额2，只会出现以下2种组合：
     * <p>
     * 3=1+1+1
     * 3=1+2
     * <p>
     * 硬币面额2不可能出现在硬币面额1之前，即不会重复计算 3=2+1 的情况。
     * print:
     * <p>
     * 14:39:31.265 [main] INFO cn.xiaolang.function.data_structure.DynamicProgramming - coin=2,dp[2]=0,dp[0]=1
     * 14:39:51.050 [main] INFO cn.xiaolang.function.data_structure.DynamicProgramming - coin=2,dp[3]=0,dp[1]=0
     * 14:39:54.026 [main] INFO cn.xiaolang.function.data_structure.DynamicProgramming - coin=2,dp[4]=0,dp[2]=1
     * 14:39:54.860 [main] INFO cn.xiaolang.function.data_structure.DynamicProgramming - coin=2,dp[5]=0,dp[3]=0
     * 14:39:56.024 [main] INFO cn.xiaolang.function.data_structure.DynamicProgramming - coin=1,dp[1]=0,dp[0]=1
     * 14:40:05.304 [main] INFO cn.xiaolang.function.data_structure.DynamicProgramming - coin=1,dp[2]=1,dp[1]=1
     * 14:40:06.357 [main] INFO cn.xiaolang.function.data_structure.DynamicProgramming - coin=1,dp[3]=0,dp[2]=2
     * 14:40:52.887 [main] INFO cn.xiaolang.function.data_structure.DynamicProgramming - coin=1,dp[4]=1,dp[3]=2
     * 14:40:55.152 [main] INFO cn.xiaolang.function.data_structure.DynamicProgramming - coin=1,dp[5]=0,dp[4]=3
     * 14:40:55.152 [main] INFO cn.xiaolang.function.data_structure.DynamicProgramming - coin=5,dp[5]=3,dp[0]=1
     * </p>
     */
    public int change(int amount, int[] coins) {
        int dp[] = new int[amount + 1];
        // 设置起始状态
        dp[0] = 1;
        for (int coin : coins) {
            // 记录每添加一种面额的零钱，总金额i的变化
            for (int i = coin; i <= amount; i++) {
                // 在上一种零钱状态的基础上增大
                // 例如对于总额5，当只有面额为1的零钱时，只有一种可能 5x1
                // 当加了面额为2的零钱时，除了原来的那一种可能外
                // 还加上了组合了两块钱的情况，而总额为5是在总额为3的基础上加上总额2来的
                // 所以就加上此时总额为3的所有组合情况
                log.info("coin={},dp[{}]={},dp[{}]={}", coin, i, dp[i], i - coin, dp[i - coin]);
                dp[i] = dp[i] + dp[i - coin];
            }
        }
        return dp[amount];
    }
}
